題目

https://leetcode.com/problems/container-with-most-water/submissions/

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

解答

C#

public class Solution {
    public int MaxArea(int[] height) {
        int length = height.Length;
            int left = 0;
            int right = length - 1;
            int max = 0;

            while(left < right)
            {
                max = Math.Max(max, Math.Min(height[left], height[right]) * (right - left));
                if (height[left] < height[right])
                    left++;
                else
                    right--;
            }
            return max;
    }
}

結果

Runtime: 100 ms, faster than 97.54% of C# online submissions.

Memory Usage: 27 MB, less than 7.14% of C# online submissions.

Time Complexity: O(n)

Space Complextiy: O(1)

為什麼我要這樣做？

這題沒有想像中的難，只要對國中數學有概念的人大概會有些想法
主要是要找出兩根柱子之間能貯存水的 最大貯存量

1. 宣告 int length 去記錄 height 的長度
2. 宣告 int left = 0，此為從 左邊 開始巡覽的 index
3. 宣告 int right = length - 1，此為從 右邊 開始巡覽的 index
4. 宣告 int max 記錄貯存最大容量
5. 宣告 while 迴圈，判斷 left 是否小於 right，若條件成立，則會繼續下一輪
   • 判斷當前的 max 與現在計算的 max 是否一樣大
     • 現在計算的 max 為 Math.Min(height[left], height[right]) * (right - left)
       • Math.Min(height[left], height[right]) 是為了找出兩邊較短的柱子，用較長的去算水會溢出來
       • (right - left) 是為了找出面積 底長
   • if(height[left] < height[right]) left++; 表示右邊柱子較長，左邊柱子需要再往右邊巡覽有沒有更長的柱子
   • else right ++; 表示與上面結論反之
6. return max; 即為找到的可貯存之最大容量

示意圖

如果看文字敘述不是很明確的話，可以看下面的示意圖。

現在巡覽到 max，算法則是

1. 找出 min(height(left), height(right)) => 7
2. 找出底長 right - leftn => 7
3. 算出面積 => 7*7 = 49

以上就是這次 LeetCode 刷題的分享啦！
如果其它人有更棒的想法及意見，請留言或寄信(t4730@yahoo.com.tw) 給我。
那我們就下回見囉